1591. Задача сапожника
Сапожнику
необходимо выполнить n работ. Каждый
день сапожник может выполнять только одну работу. Для каждой i - ой работы известно время ее
выполнения Ti и штраф Si, который каждый день должен
платить сапожник до тех пор, пока он не отдаст i - ую работу заказчику. Найти последовательность выполнения работ,
при которой сумма штрафа будет минимальной.
Вход. Состоит из нескольких тестов. Первая строка
каждого теста содержит количество работ n
(1 £ n
£ 1000), за которой следуют n строк, содержащие характеристики работ
Ti (1 £ Ti
£ 1000) и Si (1 £ Si £ 10000).
Выход. Для каждого теста в отдельной строке вывести
порядок работ, при котором сумма штрафа минимальна. При существовании
нескольких оптимальных порядков работ выводить лексикографически наименьший.
|
Пример входа |
Пример выхода |
|
4 3 4 1
1000 2 2 5 5 |
2 1 3
4 |
РЕШЕНИЕ
жадный
алгоритм
Анализ алгоритма
Рассмотрим две
работы с характеристиками T1, S1 и T2, S2.
Если сначала
будет выполняться первая работа, а потом вторая, то сумма штрафа составит
S1
* T1 + S2 * (T1 + T2)
Если за второй
будет выполняться первая работа, то в качестве штрафа следует заплатить
S2
* T2 + S1 * (T1 + T2)
Рассмотрим, при
каком условии сумма штрафа при выполнении работ 1, 2 лучше, нежели при
выполнении работ в порядке 2, 1:
S1
* T1 + S2 * (T1 + T2) < S2
* T2 + S1 * (T1 + T2)
Раскроем скобки
и приведем подобные:
S2
* T1 < S1 * T2
Или то же самое,
что
.
Пусть теперь
имеется n работ. Если существуют i - ая и j - ая работы, для которых Ti
/ Si > Tj / Sj, то поменяв их местами в последовательности
выполнения, мы уменьшим общую сумму штрафа. Таким образом, для минимизации
штрафа следует отсортировать работы по неубыванию отношения времени их
выполнения к сумме штрафа.
В случае
равенства отношения (Ti /
Si = Tj / Sj),
работы следует сортировать по возрастанию их номеров.
Пример
Отсортируем
работы по неубыванию отношения времени их выполнения к сумме штрафа:
Получим
соответственно оптимальный порядок выполнения работ, указанный в примере. Третья и
четвертая работы имеют одинаковые отношения (2 / 2 = 5 / 5), поэтому
располагаем их в порядке возрастания номеров работ.
Реализация
алгоритма
Информацию о
работах будем заносить в массив jobs, элементами которого являются вектора
длины 3. После считывания данных jobs[i][0]
содержит время выполнения i - ой
работы Ti, jobs[i][1] содержит значение штрафа Si, а jobs[i][2] содержит номер работы i.
vector<int> j(3,0);
vector<vector<int> > jobs;
Функция сортировки. Сравнение 
эквивалентно a[0] *
b[1] < b[0] * a[1]. Если отношения a[0] / b[0] и a[1] / b[1] равны, то
раньше должна следовать работа с меньшим номером. Поэтому в этом случае следует
сравнивать номера работ, которые содержатся в a[2] и b[2].
int
lt(vector<int> a, vector<int> b)
{
if (a[0] *
b[1] == b[0] * a[1]) return a[2] < b[2];
return a[0] *
b[1] < b[0] * a[1];
}
Основная часть программы. Читаем входные данные. Заполняем
массив jobs.
while(scanf("%d",&n) == 1)
{
jobs.clear();
for(i = 1; i
<= n; i++)
{
scanf("%d
%d",&j[0],&j[1]); j[2] = i;
jobs.push_back(j);
}
Сортируем работы согласно компаратору
lt.
sort(jobs.begin(),jobs.end(),lt);
Выводим результат как требуется в
условии задачи.
for(i = 0;
i < n; i++)
printf("%d ",jobs[i][2]);
printf("\n");
}
Реализация при
помощи класса
#include <cstdio>
#include <algorithm>
#define MAX 1010
using namespace std;
int
i, n, t, fine, tests;
class
Work
{
public:
int time,
fine, id;
Work (int
time = 0, int fine = 0, int id = 0) :
time(time), fine(fine), id(id) {};
};
Work
*Jobs;
int
f(Work a, Work b)
{
// a.time
b.time
// ------ < ------
// a.fine
b.fine
if (a.time *
b.fine == b.time * a.fine) return a.id <
b.id;
return a.time
* b.fine < b.time * a.fine;
}
int
main(void)
{
while(scanf("%d",&n) == 1)
{
Jobs = new
Work[n];
for(i = 0;
i < n; i++)
{
scanf("%d
%d",&t, &fine);
Jobs[i] = Work(t,fine,i+1);
}
sort(Jobs,Jobs+n,f);
for(i = 0;
i < n; i++)
printf("%d ",Jobs[i].id);
printf("\n");
delete[]
Jobs;
}
}
Java реализация
import java.util.*;
class Job
{
int s, t, id;
public Job(int s, int t, int id)
{
this.s = s;
this.t = t;
this.id = id;
}
}
public class Main
{
public static class MyFun implements Comparator<Job>
{
public int
compare(Job a, Job b)
{
if (a.s * b.t == b.s * a.t) return a.id - b.id;
return a.s * b.t - b.s * a.t;
}
}
public static void
main(String[] args)
{
Scanner con = new Scanner(System.in);
while(con.hasNext())
{
int n = con.nextInt();
ArrayList<Job> jobs = new ArrayList<Job>();
for(int i = 1; i <= n; i++)
{
int s = con.nextInt();
int t = con.nextInt();
jobs.add(new Job(s,t,i));
}
Collections.sort(jobs, new MyFun());
for(int i = 0; i < n; i++)
System.out.print(jobs.get(i).id + " ");
System.out.println();
}
con.close();
}
}